package org.example.myleet.p552;

/**
 * 官方解，三维的动态规划
 */
public class Solution {
    public int checkRecord(int n) {
        int MOD = 1000000007;
        //代表第i天，在j个A和k个L的情况下可能符合出勤奖励的记录可能数
        long[][][] dp = new long[n + 1][2][3];
        //第0天，没有A和L，并且只有一种可能，就是什么都没有
        dp[0][0][0] = 1;
        for (int i = 1; i <= n; ++i) {
            //第i天是P的情况，L清零，A保持，A为0或1的情况下，L为0、1、2各情况的可能性叠加到当前状态
            dp[i][0][0] = (dp[i][0][0] + dp[i - 1][0][0] + dp[i - 1][0][1] + dp[i - 1][0][2]) % MOD;
            dp[i][1][0] = (dp[i][1][0] + dp[i - 1][1][0] + dp[i - 1][1][1] + dp[i - 1][1][2]) % MOD;
            //第i天是A的情况，L清零，++A，A只能为0的情况下才有效，L为0、1、2各情况的可能性叠加到当前状态
            dp[i][1][0] = (dp[i][1][0] + dp[i - 1][0][0] + dp[i - 1][0][1] + dp[i - 1][0][2]) % MOD;
            //第i天是L的情况，A保持，++L，L只能为0或1的情况下才有效，将对应的状态叠加
            dp[i][0][1] = (dp[i][0][1] + dp[i - 1][0][0]) % MOD;
            dp[i][0][2] = (dp[i][0][2] + dp[i - 1][0][1]) % MOD;
            dp[i][1][1] = (dp[i][1][1] + dp[i - 1][1][0]) % MOD;
            dp[i][1][2] = (dp[i][1][2] + dp[i - 1][1][1]) % MOD;
        }
        long sum = 0L;
        //最终的结果是第i天，统计，A为0或1，L为0、1、2这几种情况的和
        sum = (sum + dp[n][0][0] + dp[n][0][1] + dp[n][0][2]) % MOD;
        sum = (sum + dp[n][1][0] + dp[n][1][1] + dp[n][1][2]) % MOD;
        return (int) sum;
    }
}
